package loengud.w14;

/**
 * Our implementation of linked list
 * for String elements.
 * 
 * Check for an example:
 * http://math.hws.edu/eck/cs124/javanotes6/source/StringList.java
 * @author Ago
 *
 */
public class StringLinkedList {
	/**
	 * Every element in the list is a Node,
	 * which has the reference to the next element.
	 */
	class Node {
		String item;
		Node next;
	}
	
	/**
	 * Keeps the reference to the head element.
	 */
	Node head = null;
	
	/**
	 * Searches the list for a specified item.
	 * @param searchItem The item that is to be searched for
	 * @return true if searchItem is one of the items in the list
	 * or false if searchItem does not occur in the list.
	 */
	public boolean find(String searchItem) {

		Node runner; // A pointer for traversing the list.

		runner = head; // Start by looking at the head of the list.
						// (head is an instance variable! )

		while (runner != null) {
			// Go through the list looking at the string in each
			// node. If the string is the one we are looking for,
			// return true, since the string has been found in the list.
			if (runner.item.equals(searchItem))
				return true;
			runner = runner.next; // Move on to the next node.
		}

		// At this point, we have looked at all the items in the list
		// without finding searchItem. Return false to indicate that
		// the item does not exist in the list.

		return false;

	} // end find()

	/**
	 * Insert a specified item to the list, keeping the list in order.
	 * 
	 * @param insertItem
	 *            the item that is to be inserted.
	 */
public void insert(String insertItem) {

	Node newNode; // A Node to contain the new item.
	newNode = new Node();
	newNode.item = insertItem; // (N.B. newNode.next is null.)

	if (head == null) {
		// The new item is the first (and only) one in the list.
		// Set head to point to it.
		head = newNode;
	} else if (head.item.compareTo(insertItem) >= 0) {
		// The new item is less than the first item in the list,
		// so it has to be inserted at the head of the list.
		newNode.next = head;
		head = newNode;
	} else {
		// The new item belongs somewhere after the first item
		// in the list. Search for its proper position and insert it.
		Node runner; // A node for traversing the list.
		Node previous; // Always points to the node preceding runner.
		runner = head.next; // Start by looking at the SECOND position.
		previous = head;
		while (runner != null && runner.item.compareTo(insertItem) < 0) {
			// Move previous and runner along the list until runner
			// falls off the end or hits a list element that is
			// greater than or equal to insertItem. When this
			// loop ends, previous indicates the position where
			// insertItem must be inserted.
			previous = runner;
			runner = runner.next;
		}
		newNode.next = runner; // Insert newNode after previous.
		previous.next = newNode;
	}

} // end insert()
}
